数论模板

BSGS

int qpow(int a,int b,int p)
{
	int res = 1 % p;
	while(b)
	{
		if(b & 1)	res = (1ll * res * a) % p;
		a = (1ll * a * a) % p;
		b >>= 1;
	}
	return res;
}
int BSGS(int a,int b,int p)
{
	map<int,int> tbl;
	int t = sqrt(p) + 1;
	for(int j = 0;j < t;++j)
	{
		int val = (1ll * b * qpow(a,j,p)) % p;
		tbl[val] = j;
	}
	a = qpow(a,t,p);
	if(a == 0)	return b == 0 ? 0 : -1;
	for(int i = 0;i <= t;++i)
	{
		int val = qpow(a,i,p);
		int j = tbl.find(val) == tbl.end() ? -1 : tbl[val];
		if(j >= 0 && i * t - j >= 0)	return i * t - j;
	}
	return -1;
}

exgcd

int exgcd(int a,int b,int& x,int& y)
{
    if(b == 0)
    {
        x = 1,y = 0;
        return a;
    }
    int d = exgcd(b,a%b,y,x);
    y -= a/b*x;
    return d;
}